# -*- coding:utf-8 -*-
# 输入一个链表，输出该链表中倒数第k个结点。
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        array = []
        while head:
            array.append(head)
            head = head.next
        if k <= 0 or k >len(array):
            return
        return array[-k]

    def FindKthToTail_opt(self, head, k):
        if not head or k == 0: return
        cur = head
        i = 1
        while i < k:
            cur = cur.next
            i += 1
            if not cur: return
        key = head
        while cur.next:
            cur = cur.next
            key = key.next
        return key

    def FindKthToTail1(self, head, k):
        def reverse(root):
            if not root: return 0, None
            x, node = reverse(root.next)
            return x+1, (root if x+1 == k else node)
        _, res = reverse(head)
        return res

s = Solution()
a1 = ListNode(1)
a2 = ListNode(2)
a3 = ListNode(3)
a4 = ListNode(4)
a5 = ListNode(5)
a4.next = a5
a3.next = a4
a2.next = a3
a1.next = a2
print(s.FindKthToTail_opt(a1,6))